package com.example.demo.tree;

import java.util.Stack;

/**
 * Created by 蔡超 on 2018/10/9.
 * 定义一个二叉树
 */
public class BinaryTreeNode<T> implements BinaryTreeNodeInterface {

    private T data;

    private BinaryTreeNode<T> leftTreeNode;

    private BinaryTreeNode<T> rightTreeNode;

    public BinaryTreeNode(T data) {
        this.data = data;
    }

    public BinaryTreeNode(T data, BinaryTreeNode<T> leftTreeNode, BinaryTreeNode<T> rightTreeNode) {
        this.data = data;
        this.leftTreeNode = leftTreeNode;
        this.rightTreeNode = rightTreeNode;
    }

    @Override
    public Object getData() {
        return data;
    }

    @Override
    public void setData(Object newData) {
        this.data = data;
    }

    @Override
    public BinaryTreeNodeInterface getLeftChild() {
        return leftTreeNode;
    }

    @Override
    public BinaryTreeNodeInterface getRightChild() {
        return rightTreeNode;
    }

    @Override
    public void setLeftChild(BinaryTreeNodeInterface leftChild) {
        this.leftTreeNode = (BinaryTreeNode<T>) leftChild;
    }

    @Override
    public void setRightChild(BinaryTreeNodeInterface rightChild) {
        this.rightTreeNode = (BinaryTreeNode<T>) rightChild;
    }

    @Override
    public boolean hasLeftChild() {
        return leftTreeNode != null;
    }

    @Override
    public boolean hasRightChild() {
        return rightTreeNode != null;
    }

    @Override
    public boolean isLeaf() {
        return leftTreeNode == null && rightTreeNode == null;
    }

    @Override
    public int getNumberOfNodes() {
        int leftNum = 0;
        int rightNum = 0;
        if(leftTreeNode != null){
            leftNum = leftTreeNode.getNumberOfNodes();
        }
        if(rightTreeNode != null){
            rightNum = rightTreeNode.getNumberOfNodes();
        }
        return 1+leftNum+rightNum;
    }

    @Override
    public int getHeight() {
        int height = 1;
        if(leftTreeNode == null && rightTreeNode == null){
            return height;
        }else{
            height = Math.max(leftTreeNode==null?0:leftTreeNode.getHeight(),
                    rightTreeNode==null?0:rightTreeNode.getHeight())
                    + 1;
            return height;
        }
    }

    @Override
    public BinaryTreeNodeInterface copy() {
        BinaryTreeNode newTreeNode = new BinaryTreeNode(data);
        if(leftTreeNode != null){
            newTreeNode.setLeftChild(leftTreeNode.copy());
        }
        if(rightTreeNode != null){
            newTreeNode.setRightChild(rightTreeNode.copy());
        }
        return newTreeNode;
    }

    @Override
    public void preOrder(BinaryTreeNodeInterface binaryTreeNodeInterface) {
        if(binaryTreeNodeInterface != null){
            System.out.println(binaryTreeNodeInterface.getData());
            preOrder(binaryTreeNodeInterface.getLeftChild());
            preOrder(binaryTreeNodeInterface.getRightChild());
        }
    }

    @Override
    public void midOrder(BinaryTreeNodeInterface binaryTreeNodeInterface) {
        if(binaryTreeNodeInterface != null){
            preOrder(binaryTreeNodeInterface.getLeftChild());
            System.out.println(binaryTreeNodeInterface.getData());
            preOrder(binaryTreeNodeInterface.getRightChild());
        }
    }

    @Override
    public void sufOrder(BinaryTreeNodeInterface binaryTreeNodeInterface) {
        if(binaryTreeNodeInterface != null){
            preOrder(binaryTreeNodeInterface.getLeftChild());
            preOrder(binaryTreeNodeInterface.getRightChild());
            System.out.println(binaryTreeNodeInterface.getData());
        }
    }

    @Override
    public void preOrderByStack(BinaryTreeNodeInterface binaryTreeNodeInterface) {
        if(binaryTreeNodeInterface != null){
            Stack stack = new Stack();
            stack.push(binaryTreeNodeInterface);
            while (!stack.empty()){
                BinaryTreeNode node = (BinaryTreeNode) stack.pop();
                if(node != null){
                    System.out.println(node.getData());
                    stack.push(node.getRightChild());
                    stack.push(node.getLeftChild());
                }
            }
        }
    }

    public static void main(String[] args) {
        BinaryTreeNode root = new BinaryTreeNode("1");
        BinaryTreeNode l2_1 = new BinaryTreeNode("21");
        BinaryTreeNode l2_2 = new BinaryTreeNode("22");

        root.setLeftChild(l2_1);
        root.setRightChild(l2_2);

        BinaryTreeNode l3_1 = new BinaryTreeNode("301");
        BinaryTreeNode l3_2 = new BinaryTreeNode("302");
        BinaryTreeNode l3_3 = new BinaryTreeNode("303");
        BinaryTreeNode l3_4 = new BinaryTreeNode("304");
        l2_1.setLeftChild(l3_1);
        l2_1.setRightChild(l3_2);

        l2_2.setLeftChild(l3_3);
        l2_2.setRightChild(l3_4);

        BinaryTreeNode l4_1 = new BinaryTreeNode("401");
        BinaryTreeNode l4_2 = new BinaryTreeNode("402");
        l3_1.setLeftChild(l4_1);
        l3_1.setRightChild(l4_2);

        System.out.println("nodeNum:" + root.getNumberOfNodes());
        System.out.println("height:" + root.getHeight());
        BinaryTreeNode newTrade = (BinaryTreeNode) root.copy();
        System.out.println(newTrade.getHeight());

        System.out.println("===========遍历============================");
        System.out.println("前序：");
        newTrade.preOrder(newTrade);
        System.out.println("中序：");
        newTrade.midOrder(newTrade);
        System.out.println("后序：");
        newTrade.sufOrder(newTrade);
        System.out.println("非递归");
        newTrade.preOrderByStack(newTrade);
    }

}
